Top K Frequent Elements

Posted on |

问题描述（难度中等-347）

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

1
2
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

1
2
Input: nums = [1], k = 1
Output: [1]

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

方法一：HashMap+PriorityQueue

复杂度分析摘录

Complexity Analysis

  • Time complexity : O(Nlog(k). The complexity of Counter method is O(N). To build a heap and output list takes O(Nlog(k)). Hence the overall complexity of the algorithm is O(N + Nlog(k)) =O(Nlog(k)).
  • Space complexity : O(N) to store the hash map.

实现代码

通过HashMap进行计算，再通过优先级队列最小堆找出前k个出现最多的。时间复杂度O(N*log(k))，空间复杂度O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

package P347;

import java.util.*;

/**
 * 先用map再用优先级队列
 */
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> integerMap=new HashMap<>();
        //统计完出现的次数
        for (int i = 0; i < nums.length; i++) {
            if (integerMap.containsKey(nums[i])) {
                Integer value=integerMap.get(nums[i]);
                integerMap.put(nums[i],++value);
            }else {
                integerMap.put(nums[i],1);
            }
        }

        /*//定义一个比较器
        Comparator<Map.Entry<Integer,Integer>> comparator=
                (entry1,entry2)-> entry1.getValue()-entry2.getValue();
*/
        //定义一个比较器  这个操作可以类比上面的函数表达式
        Comparator<Map.Entry<Integer,Integer>> comparator=
                Comparator.comparing(Map.Entry<Integer,Integer>::getValue);


        //构造优先级队列
        PriorityQueue<Map.Entry<Integer,Integer>> priorityQueue=new PriorityQueue<>(
                k,comparator
        );
        //放入优先级队列
        integerMap.entrySet().forEach(integerIntegerEntry -> {
            if (priorityQueue.size()<k) {
                priorityQueue.offer(integerIntegerEntry);
            }else {
                Map.Entry<Integer,Integer> top=priorityQueue.peek();
                if (comparator.compare(integerIntegerEntry,top)>0) {
                    priorityQueue.poll();
                    priorityQueue.offer(integerIntegerEntry);
                }
            }
        });
        List<Integer> result=new ArrayList<>();
        //获取k大的key
        Iterator<Map.Entry<Integer,Integer>> iterator=priorityQueue.iterator();
        while (iterator.hasNext()) {
            result.add(iterator.next().getKey());
        }
        return result;
    }

    public static void main(String[] args) {
        int[] ints={4,1,-1,2,-1,2,3};
        new Solution().topKFrequent(ints,2);

        int[] ints1={1};
        new Solution().topKFrequent(ints1,1);
    }
}

这里主要需要定义一个比较器，传送给PriorityQueue。

方法二：Map+TreeMap

这个方法相当于对搜集的结果进行全排序，时间复杂度O(N*log(N)),空间复杂度O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package P347;
import java.util.*;

/**
 * @autor yeqiaozhu.
 * @date 2019-10-11
 */
public class UsingTreeMap {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> countMap=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            countMap.put(nums[i],countMap.getOrDefault(nums[i],0)+1);
        }

        TreeMap<Integer,List<Integer>> treeMap= new TreeMap<>();
        for(int num : countMap.keySet()){
            int freq = countMap.get(num);
            if(!treeMap.containsKey(freq)){
                treeMap.put(freq, new LinkedList<>());
            }
            treeMap.get(freq).add(num);
        }

        List<Integer> res = new ArrayList<>();
        while(res.size()<k){
            Map.Entry<Integer, List<Integer>> entry = treeMap.pollLastEntry();
            res.addAll(entry.getValue());
        }

        return res;
    }

    public static void main(String[] args) {
        int[] ints={4,1,-1,2,-1,2,3};
        int[] ints1={1};
        new UsingTreeMap().topKFrequent(ints,2);
        new UsingTreeMap().topKFrequent(ints1,1);
    }
}